package problems.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 119. 杨辉三角II
 * https://leetcode.cn/problems/pascals-triangle-ii/
 * @author habitplus
 * @since 2022/8/3 21:54
 */
public class T119 {
    public List<Integer> getRow(int rowIndex) {
        if (rowIndex < 0) return new ArrayList<>();

        List<Integer> list = new ArrayList<>(rowIndex + 1);
        int[] ans = new int[rowIndex + 1];
        for (int i = 0; i <= rowIndex; i++) {
            // 从后往前遍历，再根据对称性，直接减半
            for (int j = i/2; j >= 0; j--) {
                if (j == 0) ans[j] = ans[i] = 1;
                else {
                    ans[j] = ans[i - j] = ans[j] + ans[j-1];
                }
            }
        }

        for (int i = 0; i <=rowIndex; i++) {
            list.add(ans[i]);
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(new T119().getRow(4));
    }
}
